/*
 * Program HW 1 Compute Prefix Sum with MPI
 * Name: Songgang Xu
 * Email sxu@tamu.edu
 */

/*
 * prefix_sum.mpi.c - Description:
 * Compute prefix_sum using MPI
 * User specify the number of random integers and the number of processors
 * Show the time elapse display
 */ 

#include <stdlib.h>
#include <time.h>
#include <sys/resource.h>
#include <mpi.h>
#include <math.h>


/*
 * Generate Random Integers  */
void generateRandomIntegers (int * memory, int n) {

	int i;
	for (i=0; i<n; i++) {
		memory[i] = rand();
	}

	return;

}

/*
 * printElapsed (calculate & print out time elapsed)
 */
void printElapsed (char * desc, struct timeval * start, struct timeval * end, int niters) {
	struct timeval elapsed;

	if (start -> tv_usec > end -> tv_usec) {
		end -> tv_usec += 1000000;
		end -> tv_sec--;
	}

	elapsed.tv_usec = end -> tv_usec - start -> tv_usec;
	elapsed.tv_sec = end ->tv_sec - start -> tv_sec;

	printf("\n %s total elapsed time = %1d (usec)",
		   desc, (elapsed.tv_sec*1000000 + elapsed.tv_usec)/niters);

	return;

}/* printElapsed() */


/*
 * prefixSum 
 * Compute partial result of prefix sum using 'pointer jumping' algorithm
 * Receive partial result from last process (process 0 exempts)
 * Add this partial result to each element
 * pass the result of the last element to the next process (process (nrocs - 1) exempts)
 */
void prefixSum (int * memints, int pid, int numelts, int nprocswork, MPI_Status status ) {
	int * partial_sum;                    /* receive the prefix sum of the last element the last processor computes */
	int pre_par_sum;                          /* sum of all the last elements in the previous process */

	int pre, suc;                   /* preceding processor and success processor */
	int * predecmem, * succesmem;         /* memory for predecessor and successor */

 
	partial_sum = (int *)malloc(sizeof(int));
	predecmem = (int *)malloc(sizeof(int));
	succesmem = (int *)malloc(sizeof(int));
  
	if (!partial_sum || !predecmem || !succesmem) {
		printf("Processor %d - unable to malloc when computing prefixsums", pid);
		exit(1);
	}

	/*----------------------------------------------------------------------
	 * use 'pointer jumping' to compute prefix sum
	 *---------------------------------------------------------------------*/
	pre_par_sum = 0;                                       /* set pre_par_sum to 0 */

	/* initially set the predecessor of each process to the index of the process directly in front of it */
	/* process 0 is set to -1 */ 
	if (pid == 0) {
		pre = -1;
	} else {
		pre = pid - 1;
	}

	/* initially set the successor of each process */
	/* the last process is set to -1 */
	if (pid == nprocswork - 1) {
		suc = -1;
	} else {
		suc = pid + 1;
	} 

	/* sequentially compute the prefix sums */
	int i;
	for (i = 1; i < numelts; i++) {
		memints[i] += memints[i - 1];
	}

	/* Pointer jumping*/
	while (pre != -1 && suc != -1) {
		MPI_Recv(partial_sum, 1, MPI_INT, pre, 0, MPI_COMM_WORLD, &status);  /* receive the previous partial sum */
		MPI_Recv(predecmem, 1, MPI_INT, pre, 1, MPI_COMM_WORLD, &status);    /* receive the index of predecessor */
		MPI_Send(&suc, 1, MPI_INT, pre, 2, MPI_COMM_WORLD);               /* send the index to its predecessor */
		MPI_Send(&memints[numelts - 1], 1, MPI_INT, suc, 0, MPI_COMM_WORLD); /* send the last sum to its successor */
		MPI_Send(&pre, 1, MPI_INT, suc, 1, MPI_COMM_WORLD);               /* send the index to its successor */
		MPI_Recv(succesmem, 1, MPI_INT, suc, 2, MPI_COMM_WORLD, &status);    /* receive the index of successor */
		pre_par_sum += (* partial_sum);
		pre = (* predecmem);
		suc = (* succesmem);
	}
	if (pre == -1) {
		while (suc != -1) {
			MPI_Send(&memints[numelts - 1], 1, MPI_INT, suc, 0, MPI_COMM_WORLD); /* send the last sum to its successor */ 
			MPI_Send(&pre, 1, MPI_INT, suc, 1, MPI_COMM_WORLD);               /* send the index to its successor */
			MPI_Recv(succesmem, 1, MPI_INT, suc, 2, MPI_COMM_WORLD, &status);    /* receive the index of successor */
			suc =(* succesmem);
		}
	} else if (suc == -1) {
		while (pre != -1) {
			MPI_Recv(partial_sum, 1, MPI_INT, pre, 0, MPI_COMM_WORLD, &status);  /* receive the previous sum */
			MPI_Recv(predecmem, 1, MPI_INT, pre, 1, MPI_COMM_WORLD, &status);    /* receive the index of the predecessor */
			MPI_Send(&suc, 1, MPI_INT, pre, 2, MPI_COMM_WORLD);               /* send the index to the predecessor */
			pre_par_sum += (* partial_sum);
			pre =(* predecmem);
		}
	}

	/*----------------------------------------------------------------------
	 * add the previous partial sum to each element
	 *----------------------------------------------------------------------*/
	for (i = 0; i < numelts; i++) {
		memints[i] += pre_par_sum;
	}
	/*----------------------------------------------------------------------
	 * clean up
	 *---------------------------------------------------------------------*/
	free(partial_sum);
	free(predecmem);
	free(succesmem);
	return;

}/* prefixSum() */


/*
 *    Main Program (Parallel Computing Prefix Sum)
 */
int  main (int argc, char ** argv) {
	int nprocs, numints;                    /* command line arguments */

	int nprocswork;                        /* num of processed actually work */

	int my_id;

	int numelts;                           /* the number of elements current process should compute  */
	int * memints;                         /* pointer to memory allocated for ints */

	struct timeval tmstart, tmend;         /* record the start time and the end time of the algorithm */
	struct timeval genstart, genend;       /* record the start time and the end time of generation random integers */
	struct timezone tzp;                   /* used in gettimeofday */


	MPI_Status status;                     /* status for MPI operations */

    
	/*---------------------------------------------------------------------
	 * Initializing MPI environment
	 * Checking the arguments
	 * 'nproc' copies of this program will be initiated by MPI  
	 * 'numints' is initiated by usr 
	 * Calculate num of elements current process should compute
	 * Allocate memory and generate integers randomly
	 * Process 0 prints the time elapsed for integer generation
	 * Compute prefix sums
	 * Process 0 prints the time elapsed for the operation above
	 *---------------------------------------------------------------------*/

	MPI_Init(&argc, &argv);

	MPI_Comm_rank(MPI_COMM_WORLD, &my_id);/* get id of this process */

	if (argc<2) {
		if (my_id == 0) {
			printf("Usage : %s [numints]\n", argv[0]); 
		}
		MPI_Finalize();
		return 0;

	}/* checking arguments */

	numints = atoi(argv[1]);
	MPI_Comm_size(MPI_COMM_WORLD, &nprocs);

    /*The maximum number of processors*/
	if (nprocs > 256) {
		if (my_id == 0) {
			printf("Usage : %s [numints] processors overflow\n", argv[0]);
		}
		MPI_Finalize();
		return 0;
	}/* checking arguments  nprocs should no more than 16 */

	if (my_id == 0) {
		printf("\nnumber of integers = %d, number of processors = %d\nExecuting %s ...\n", numints, nprocs, argv[0]);
	}

	/*-----------------------------------------------------------------------------------------------
	 * calculate  num of elements current process should compute
	 *----------------------------------------------------------------------------------------------*/
	if (numints < nprocs) {
		nprocswork = numints;
		if (my_id > numints) {
			numelts = 0;
		}
		else {
			numelts = 1;
		}
	}/* num of ints less than num of processes */
	else {
		nprocswork = nprocs;
		int subsize = numints / nprocs;
		if (my_id != nprocs -1) {
			numelts = subsize;
		}/* num of elements of the first nprocs - 1 processes  */
		else {
			numelts = numints - (nprocs - 1) * subsize;
		}/* num of elements of the last process  */
	}/* num of ints no less than num of processes */

	MPI_Barrier(MPI_COMM_WORLD);

	if (numelts != 0) {
		memints = (int *)malloc(sizeof(int) * numelts);

		if (!memints) {
			printf("Processor %d - unable to malloc()\n", my_id);
			return 0;
		}
	}/* allocate memory for integers */

	MPI_Barrier(MPI_COMM_WORLD);

	if (my_id == 0) {
		gettimeofday(&genstart, &tzp);
	}/* time elapsed stuff */

	if (numelts != 0) {
		generateRandomIntegers(memints, numelts);
	}

	MPI_Barrier(MPI_COMM_WORLD);


	if (my_id == 0) {
		gettimeofday(&genend, &tzp);
		printElapsed("GenInts", &genstart, &genend, 1);
		gettimeofday(&tmstart, &tzp);
	}/* time elapsed stuff */


	/*-------------------------------------------------------------------------------------------------
	 * compute prefix sums parallel
	 *------------------------------------------------------------------------------------------------*/
	if (numelts != 0) {
		prefixSum(memints, my_id, numelts, nprocswork, status);
	}

	MPI_Barrier(MPI_COMM_WORLD);
 
	if (my_id == 0) {
		gettimeofday(&tmend, &tzp);
		printElapsed("ComputePrefixSums", &tmstart, &tmend, 1);
		printf("\n");
	}/* time elapsed stuff */

	/*--------------------------------------------------------------------------------------------------
	 * cleanup free memory
	 *-------------------------------------------------------------------------------------------------*/
	free(memints);

	MPI_Finalize();

	return 0;





}/* main() */
